Not Applicable
1. Field of the Invention
This invention pertains generally to the analysis of the variability of multimedia traffic sources and the provisioning of the Quality-of-Service parameters and more particularly to a method of determining burstiness, and burstiness curves, for a multimedia source.
2. Description of the Background Art
The explosive growth of the Internet has spawned demand for new applications whose traffic has been traditionally carried over switched networks. These new applications include audio telephony, video conferencing and video-on-demand (VoD) services. New standards are emerging to support these applications in the context of both connectionless and connection-oriented packet-switched networks.
The rate variability of traffic sources, especially video, have introduced the need for characterizing the traffic so that the appropriate resources may be allocated by the network when handling the traffic, for instance, during the call admission control (CAC) process. Numerous resources may require allocation, including bandwidth, and buffer space. Traffic characterization may also be applied to facilitate policing of the traffic on the packet-switched network.
Characterization of video sources has become increasingly important as a result of transporting video over packet-switched networks. One method that provides characterization of a traffic source is through employing a time-invariant traffic constraint function in which bounds are determined for the maximum number of bits that may be generated by the source over any arbitrary interval of time. The least upper bound of the time constraint function is also referred to as the minimum envelope process or empirical envelope. Accurate traffic characterization can be performed for a source by the minimum envelope process, however, such a process requires the use of a large number of xe2x80x9cleaky bucketsxe2x80x9d to effectively police the traffic, and the practical significance of the process is thereby compromised. Since current packet-switched networks employ simple leaky-bucket mechanisms for traffic policing, the use of the minimum envelope process does not facilitate traffic policing.
Another method of characterizing a traffic source is by means of its burstiness curve. The points ("sgr",xcfx81) along the burstiness curve correspond to maximum queue size "sgr" that is necessary when said traffic source is fed into a server having a deterministic service rate xcfx81. Consequently, if the traffic source is sent to a leaky bucket with parameters ("sgr",xcfx81), none of its packets will be tagged as non-conformant. The burstiness curve, therefore, provides an attractive metric for use in policing current packet-switched networks and for allocating resources.
Burstiness curves are typically characterized by means of a token-bucket mechanism. The input of the token-bucket is the traffic generated by the source whereas the output is the corresponding token-bucket constrained traffic. The output of the token bucket is sometimes referred to as a ("sgr",xcfx81,r) conformant traffic stream, where "sgr" is the number of tokens in the token bucket, xcfx81 the rate of the incoming tokens, and r the peak rate of the server. If A(t1, t2) is the amount of traffic that leaves the token bucket during an interval (t1, t2), then the following constraint holds:
A(t1, t2)xe2x89xa6min{r(t1xe2x88x92t2),"sgr"+xcfx81(t2xe2x88x92t1)}xe2x80x83xe2x80x83(1) 
A traffic source is said to be ("sgr",xcfx81,r) conformant if its traffic can go through a token-bucket shaper with bucket size "sgr" and rate xcfx81, at peak rate r with the queue size never exceeding "sgr". In the context of ATM networks, ("sgr",xcfx81,r) enforcement is provided by utilizing the Generalized Cell-Rate Algorithm (GCRA).
Specifying an appropriate ("sgr",xcfx81,r) tuple for the traffic source is critical to the proper allocation of resources, for instance bandwidth and buffer space, in providing a desired level of service to the traffic stream. However, there is no single tuple that uniquely characterizes a source. For any given peak rate r, it is evident from Eq. (1) that, for any value of xcfx81, there is a corresponding value of "sgr" such that the source is conformant. Hence, the set of conformant ("sgr",xcfx81) pairs describe a curve which is referred to as the burstiness curve. Complete characterization of a source can be provided by plotting a set of burstiness curves for different values of the peak rate r. The burstiness curve of a video source is useful in determining the level of resources necessary to achieve any desired QoS level. It will be appreciated that both the delay and packet-loss rate in the network are functions of "sgr" and xcfx81. Knowledge of the burstiness curve of the source, therefore, enables the admission control process to allocate the minimum level of resources to achieve a desired QoS level.
In addition, the delay calculation in the network depends on the burstiness curve of the source. A properly configured packet-switched network scheduler based on burstiness curves allows for the specification of a maximum end-to-end guaranteed delay time. The specification of end-to-end delay of a traffic source requires utilizing algorithms configured for adherence to a strict upper bound on the delay of a session. It will be appreciated, however, that in order for a scheduling discipline to guarantee a worst-case delay bound to a session, the burstiness of the source traffic must be bounded. Analysis of worst-case delay is typically considered in relation to a token-bucket constrained traffic model. Different frameworks have been developed to formalize the characterization of schedulers and obtain the worst-case boundaries of delay. One such framework is that of xe2x80x9cLatency-ratexe2x80x9d (LR) which provides a general model for computation of the worst-case delay bound of several schedulers. Schedulers that fall into this classification are often referred to as Latency-Rate (LR) servers.
In utilizing the LR model it is assumed that the bandwidth allocated by the network to the session is equal to the average rate of the source xcfx81. According to the LR model, the worst-case delay bound dM of a tandem network consisting of K schedulers belonging to the LR class is given by:                               ⅆ          M                ⁢                  =                                    σ              ρ                        +                                          ∑                                  i                  =                  1                                K                            ⁢                              xe2x80x83                            ⁢                              Θ                i                                                                        (        2        )            
where "sgr", xcfx81 are the parameters of the source, and "THgr"i is a parameter of the scheduler, called latency. Solving for "sgr", the following constraint for "sgr" and xcfx81 is obtained which satisfies a specified worst-case delay bound:                     σ        =                              (                                          ⅆ                M                            ⁢                              -                                                      ∑                                          i                      =                      1                                        K                                    ⁢                                      xe2x80x83                                    ⁢                                      Θ                    i                                                                        )                    ⁢          ρ                                    (        3        )            
Upon considering the result it will be recognized that the optimum ("sgr",xcfx81) pair is obtained at the intersection between the line defined by Eq. (3) and the burstiness curve.
Determination of the burstiness curve typically relies on simulation based techniques, with results obtained subsequent to a lengthy simulation session. Simulation techniques are considered especially onerous when fine rate granularity is required. Conventional methods are unable to readily determine burstiness, and burstiness curves to any desired level of granularity.
Therefore, a needs exists for an improved method of determining burstiness and burstiness curves wherein both exact determinations and approximations can be performed in less time while preferably utilizing fewer processing resources. The present invention satisfies those needs, as well and others, and overcomes the deficiencies of prior solutions.
The present invention provides methods for determining burstiness and burstiness curves for traffic streams, typified by multimedia streams such as video and audio. By way of example and not of limitation, the detailed embodiments describe burstiness computation methods tailored for use with both elementary video streams and MPEG-2 transport streams. These burstiness computation methods exploit the piecewise linearity that exists within the burstiness curves of traffic streams. The methods are capable of ascertaining the minimum number of requisite points in order to compute exact results. Therefore, the methods of the present invention are optimal with regard to the number of points necessary for computing an exact result for a burstiness curve. In addition, an approximate version of the method is described which reduces the computational effort by considering a smaller number of candidate points of known significance. The methods exhibit efficiency with regard to both time and space in comparison with traditional simulation-based approaches. It is anticipated that the high efficiency of the proposed methods proffer their use within a number of application areas, which include but are not limited to, video servers which compute burstiness curves of video traces for storage as metadata with the trace for QoS control, and real-time video distribution systems that need to estimate the burstiness curve of their video programs in real-time.
The method of the invention determines the computation and selection process for the traffic parameters of a multimedia traffic source. The traffic parameters are considered crucial for the correct provisioning and dimensioning of network resources in the case of transmission over a packet network. The method simulates a token-bucket traffic policing mechanism to analyze the traffic source which leads to an exact burstiness curve computation. The burstiness curve determination methods can be applied to any multimedia traffic source, and therefore, to both elementary video streams and MPEG-2 Transport Streams. The method exploits the piecewise linearity of the burstiness curve and restricts computation to those points at which the slope of the burstiness curve changes. In addition, an approximate version of the burstiness curve determination method is presented which saves computational effort by considering only those candidate points along the curve at which the slope of the burstiness curve may change. The approximate method is capable of providing results, suitable for numerous applications, in substantially less time. For example, in computing burstiness for a two-hour long elementary video stream, the approximate method according to the present invention determined the curve in approximately ten seconds with virtually no loss of accuracy in relation to the exact method which required a period of over six hours to perform the computations. The efficiency of the proposed methods are well suited for a range of applications including QoS provisioning in both off-line environments, such as in Video-on-Demand (VoD) servers, and in real-time applications, such as live TV distribution systems.
An object of the invention is to provide an efficient method of determining exact burstiness curves for multimedia streams.
Another object of the invention is to provide a method of exactly determining burstiness that is operable with both elementary video streams and MPEG-2 transport streams.
Another object of the invention is to provide a method which exploits the piecewise linearity of the burstiness curves so as to reduce necessary computation resources.
Another object of the invention is to provide a method of exactly determining burstiness in which the minimum number of subject points need be identified during computation.
Another object of the invention is to provide a method of determining burstiness and burstiness curves that can be performed in less time for a given accuracy level.
Another object of the invention is to provide a computationally space-efficient method of determining burstiness.
Another object of the invention is to provide a method of determining burstiness which is compatible with video servers.
Another object of the invention is to provide a method of determining burstiness which is compatible with real-time video distribution systems.
Further objects and advantages of the invention will be brought out in the following portions of the specification, wherein the detailed description is for the purpose of fully disclosing preferred embodiments of the invention without placing limitations thereon.